// OpentTxl-C Version 11 parse tree representation
// J.R. Cordy, Jan 2023

// Copyright 2023, James R. Cordy and others

// Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
// and associated documentation files (the “Software”), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all copies 
// or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
// AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// OpenTxl Parse Trees.
// Defines and maintains the parse tree structures used to represent grammar trees, 
// parse trees, rule pattern trees and rule replacement trees.  

// Trees are structured as tree nodes and kids, in the traditional Lisp cons() fashion

// I.E., the tree:        Is represented as:
//
//            X                 X--+-------------+
//           / \                   |             |
//          Y   Z                  Y--+--+--+    Z
//          /|\                       |  |  |
//         / | \                              A  B  C--+--+
//       A  B  C                               |  |
//             / \                             D  E
//            D   E

// where each label is a tree node, and each tree has a sequential list of kids (+'s) 
// linking to the child tree nodes of the tree.

// Modification Log

// v11.0 Initial revision, adapted from OpenTxl 11.0

// I/O, strings, memory allocation
#include "support.h"

// Global modules
#include "limits.h"
#include "options.h"
#include "tokens.h"
#include "idents.h"
#include "shared.h"
#include "errors.h"

// Check interface consistency
#include "trees.h"

// Error message construction outside of procedures, to avoid using stack space
string outOfTreesMessage;
string outOfKidsMessage;

// Tree and kids arrays, allocated dynamically
// We assume that trees and kids are initialized to 0 when allocated
array (struct parseTreeT, tree_trees);
array (treePT, tree_kids);

// Numbers of trees and kids currently in use
int tree_treeCount;
int tree_maxTreeCount;
int tree_kidCount;

// Current allocation strategy
// two are implemented - 
//      simple = haven't run out yet, so linearly use unused cells
//      scavenge = have done a garbage collection, so search for first fit
int tree_allocationStrategy;

void tree_setTreeCount (const int count)
{
    tree_treeCount = count;
}

void tree_setKidCount (const int count)
{
    tree_kidCount = count;
}

void tree_setAllocationStrategy (const int strategy)
{
    tree_allocationStrategy = strategy;
}

// next free tree/kid search starting point (when scavenging)
static int tree_lookTree;
static int tree_lookKid;

treePT tree_newTree (void) {
    treePT nt = nilTree;

    if (tree_allocationStrategy == simple) {
        // Haven't yet done a garbage collection, using simple linear allocation
        while (true) {
            if (tree_treeCount == maxTrees) {
                // Ran out - cause a garbage collection
                if (!(options_option[quiet_p])) {
                    error ("", outOfTreesMessage, DEFERRED, 981);
                }
                throw (OUTOFTREES);
            }
            tree_treeCount++; 
            if ((tree_treeCount > tree_maxTreeCount) || (tree_trees[tree_treeCount].kind < firstLiteralKind)) 
                break;
        }

        nt = tree_treeCount;

        if (tree_treeCount > tree_maxTreeCount) {
            tree_maxTreeCount = tree_treeCount;
        }

    } else {
        // Done a garbage collection, so using first fit search allocation
        treePT lt = tree_lookTree;
        const treePT startLook = tree_lookTree;
        while (true) {
            lt++;
            if (lt > maxTrees) {
                lt = 1;
            }
            if (tree_trees[lt].kidsKP == AVAILABLE) {
                nt = lt;
                tree_treeCount++;
                tree_lookTree = lt;
                break;
            }
            if (lt == startLook) break;
        }

        if (nt == 0) {
            if (!(options_option[quiet_p])) {
                error ("", outOfTreesMessage, DEFERRED, 981);
            }
            throw (OUTOFTREES);
        }
    }

    assert (nt != nilTree);
    tree_trees[nt].kidsKP = nilKid;

    return (nt);
}

void tree_cloneTree (const treePT nt, const treePT ot)
{
    structassign (tree_trees[nt], tree_trees[ot]);
}

treePT tree_newTreeClone (const treePT ot)
{
    const treePT nt = tree_newTree ();
    structassign (tree_trees[nt], tree_trees[ot]);
    return (nt);
}

treePT tree_newTreeInit (const enum treeKindT kind, const tokenT name, const tokenT rawname, const countT count, const kidPT kidsKP)
{
    const treePT nt = tree_newTree ();
    tree_trees[nt].kind = kind;
    tree_trees[nt].name = name;
    tree_trees[nt].rawname = rawname;
    tree_trees[nt].count = count;
    tree_trees[nt].kidsKP = kidsKP;
    return (nt);
}

void tree_setKind (const treePT t, const enum treeKindT kind)
{
    tree_trees[t].kind = kind;
}

void tree_setName (const treePT t, const tokenT name)
{
    tree_trees[t].name = name;
}

void tree_setRawName (const treePT t, const tokenT rawname)
{
    tree_trees[t].rawname = rawname;
}

void tree_setKids (const treePT t, const kidPT kidsKP)
{
    tree_trees[t].kidsKP = kidsKP;
}

void tree_setCount (const treePT t, const countT count)
{
    tree_trees[t].count = count;
}

void tree_setDerivesEmpty (const treePT t, const enum derivesT setting)
{
    tree_trees[t].derivesEmpty = setting;
}

kidPT tree_newKid (void) {
    kidPT nk = nilKid;

    if (tree_allocationStrategy == simple) {
        // Haven't yet done a garbage collection, using simple linear allocation
        if (tree_kidCount == maxKids) {
            // Ran out - cause a garbage collection
            if (!(options_option[quiet_p])) {
                error ("", outOfKidsMessage, DEFERRED, 984);
            }
            throw (OUTOFKIDS);
        }
        tree_kidCount++;
        nk = tree_kidCount;

    } else {
        // Done a garbage collection, using first fit search allocation
        kidPT lk = tree_lookKid;
        const kidPT startLook = tree_lookKid;
        while (true) {
            lk++;
            if (lk > maxKids) {
                lk = 1;
            }
            if (tree_kids[lk] == AVAILABLE) {
                nk = lk;
                tree_kidCount++;
                tree_lookKid = lk;
                break;
            }
            if (lk == startLook) break;
        }
        if (nk == nilKid) {
            if (!(options_option[quiet_p])) {
                error ("", outOfKidsMessage, DEFERRED, 984);
            }
            throw (OUTOFKIDS);
        }
    }

    assert (nk != nilKid);
    tree_kids[nk] = nilTree;

    return (nk);
}

kidPT tree_newKids (const countT count)
{
    kidPT nk = nilKid;

    if (tree_allocationStrategy == 0) {
        // Haven't yet done a garbage collection, using simple linear allocation
        if (tree_kidCount + count > maxKids) {
            if (!(options_option[quiet_p])) {
                error ("", outOfKidsMessage, DEFERRED, 984);
            }
            throw (OUTOFKIDS);
        }
        nk = tree_kidCount + 1;
        tree_kidCount += count;

    } else {
        // Done a garbage collection, using first fit search allocation
        kidPT lk = tree_lookKid;
        const kidPT startLook = tree_lookKid;
        while (true) {
            lk++;
            if (lk + count - 1 > maxKids) {
                if (startLook >= lk) break;
                lk = 1;
            }

            if (tree_kids[lk] == AVAILABLE) {
                if (count == 1) {
                    nk = lk;
                    tree_kidCount++;
                    tree_lookKid = lk;
                    break;

                } else if (count == 2) {
                    // Common case - avoid loop overhead
                    if (tree_kids[lk + 1] == AVAILABLE) {
                        nk = lk;
                        tree_kidCount += 2;
                        lk++;
                        tree_lookKid = lk;
                        break;
                    } else {
                        lk++;
                    }

                } else {
                    const kidPT lkend = (lk + count) - 1;
                    kidPT lkn = lk + 1;
                    for (;;) {
                        if (tree_kids[lkn] != AVAILABLE) {
                            lk = lkn;
                            break;
                        }

                        if (lkn == lkend) {
                            nk = lk;
                            tree_kidCount += count;
                            tree_lookKid = lkend;
                            break;
                        }

                        lkn++;
                    }
                }
            }

            if ((nk != 0) || (lk == startLook)) break;
        }

        if (nk == 0) {
            if (!(options_option[quiet_p])) {
                error ("", outOfKidsMessage, DEFERRED, 984);
            }
            throw (OUTOFKIDS);
        }
    }

    for (kidPT k = nk; k <= (nk + count) - 1; k++) {
        tree_kids[k] = nilTree;
    }

    return (nk);
}

void tree_setKidTree (const kidPT k, const treePT t)
{
    tree_kids[k] = t;
}

treePT tree_firstUserTree;
kidPT  tree_firstUserKid;

void tree_beginUserTreeSpace (void) {
    tree_firstUserTree = tree_treeCount;
    tree_firstUserKid = tree_kidCount;
}

// General tree operations

// Fast whole tree operations - used in transformer and predefineds   

bool tree_sameTrees (const treePT tree1TP, const treePT tree2TP)
{
    // Stack use limitation - to avoid crashes
    checkstack ();

    switch (tree_trees[tree1TP].kind) {
        case treeKind_empty:
            {
                return (tree_trees[tree2TP].kind == 10);
            }
            break;

        case treeKind_choose:
            {
                return (((tree_trees[tree1TP].name == tree_trees[tree2TP].name) 
                    && (tree_trees[tree1TP].kind == tree_trees[tree2TP].kind)) 
                    && tree_sameTrees (tree_kids[tree_trees[tree1TP].kidsKP], tree_kids[tree_trees[tree2TP].kidsKP]));
            }
            break;

        case treeKind_order: case treeKind_repeat: case treeKind_list:
            {
                if ((tree_trees[tree1TP].name == tree_trees[tree2TP].name) 
                        && (tree_trees[tree1TP].kind == tree_trees[tree2TP].kind)) {
                    kidPT tree1KidsKP = tree_trees[tree1TP].kidsKP;
                    kidPT tree2KidsKP = tree_trees[tree2TP].kidsKP;
                    assert (tree_trees[tree1TP].count == tree_trees[tree2TP].count);
                    for (kidPT k = 1; k <= tree_trees[tree1TP].count; k++) {
                        if (!tree_sameTrees (tree_kids[tree1KidsKP], tree_kids[tree2KidsKP])) {
                            return (false);
                        };
                        tree1KidsKP++;
                        tree2KidsKP++;
                    }
                    return (true);
                } else {
                    return (false);
                }
            }
            break;

        default :
            {
                return ((tree_trees[tree1TP].kind == tree_trees[tree2TP].kind) 
                    && (tree_trees[tree1TP].name == tree_trees[tree2TP].name));
            }
            break;
    }
}

static void tree_real_copyTree (const treePT originalTP, treePT *copyTP)
{
    checkstack ();

    switch (tree_trees[originalTP].kind) {
        // These are always ok.
        case treeKind_empty: case treeKind_literal: case treeKind_key: case treeKind_token: case treeKind_stringlit:
        case treeKind_charlit: case treeKind_number: case treeKind_floatnumber: case treeKind_decimalnumber:
        case treeKind_integernumber: case treeKind_id: case treeKind_upperlowerid: case treeKind_upperid:
        case treeKind_lowerupperid: case treeKind_lowerid: case treeKind_comment: case treeKind_space: case treeKind_newline:
        case treeKind_srclinenumber: case treeKind_srcfilename: case treeKind_usertoken1: case treeKind_usertoken2:
        case treeKind_usertoken3: case treeKind_usertoken4: case treeKind_usertoken5: case treeKind_usertoken6:
        case treeKind_usertoken7: case treeKind_usertoken8: case treeKind_usertoken9: case treeKind_usertoken10:
        case treeKind_usertoken11: case treeKind_usertoken12: case treeKind_usertoken13: case treeKind_usertoken14:
        case treeKind_usertoken15: case treeKind_usertoken16: case treeKind_usertoken17: case treeKind_usertoken18:
        case treeKind_usertoken19: case treeKind_usertoken20: case treeKind_usertoken21: case treeKind_usertoken22:
        case treeKind_usertoken23: case treeKind_usertoken24: case treeKind_usertoken25: case treeKind_usertoken26:
        case treeKind_usertoken27: case treeKind_usertoken28: case treeKind_usertoken29: case treeKind_usertoken30:

        // These depend on the fact that the transformer
        // does not actually change the original tree values 
        // when matching patterns.
        case treeKind_firstTime: case treeKind_subsequentUse:

        // These depend on the fact that the transformer
        // does not actually substitute anything into a rule call
        // subtree when implementing the call.
        case treeKind_expression: case treeKind_lastExpression: case treeKind_ruleCall:
            {
                *copyTP = originalTP;
            }
            break;

        case treeKind_choose: case treeKind_leftchoose:
            // Cannot be blindly shared, and always has a child
            {
                *copyTP = tree_newTreeClone (originalTP);
                tree_trees[*copyTP].kidsKP = tree_newKid ();
                tree_real_copyTree (tree_kids[tree_trees[originalTP].kidsKP], &(tree_kids[tree_trees[*copyTP].kidsKP]));
            }
            break;

        case treeKind_order: case treeKind_repeat: case treeKind_list:
            // Cannot be blindly shared, and always has children
            {
                *copyTP = tree_newTreeClone (originalTP);

                // pre-reserve the kids to keep them contiguous 
                kidPT copyKidsKP = tree_newKids (tree_trees[originalTP].count);
                tree_trees[*copyTP].kidsKP = copyKidsKP;

                // now copy the kids over
                kidPT originalKidsKP = tree_trees[originalTP].kidsKP;
                for (kidPT k = 1; k <= tree_trees[originalTP].count; k++) {
                    tree_real_copyTree (tree_kids[originalKidsKP], &(tree_kids[copyKidsKP]));
                    originalKidsKP++;
                    copyKidsKP++;
                }
            }
            break;

        default :
            {
                error ("", "Fatal TXL error in copyTree", INTERNAL_FATAL, 971);
            }
            break;
    }
}

void tree_copyTree (const treePT originalTP, treePT *copyTP)
{
    assert (originalTP != nilTree);

    // The following logic forces the copy to be done to a temporary, 
    // without destroying the original target tree until the copy is completely successfully done.
    // This makes copyTree an atomic operation, which is necessary for garbage collection.

    treePT atomicCopyTP = nilTree;
    tree_real_copyTree (originalTP, &(atomicCopyTP));
    *copyTP = atomicCopyTP;
}

// General tree operations - used everywhere

treePT tree_kidTP (int which, treePT parentTP)
{
    return (tree_kids[tree_trees[parentTP].kidsKP + which - 1]);
}

treePT tree_kid1TP (const treePT treeP)
{
    return (tree_kids[tree_trees[treeP].kidsKP]);
}

treePT tree_kid2TP (const treePT treeP)
{
    return (tree_kids[(tree_trees[treeP].kidsKP) + 1]);
}

treePT tree_kid3TP (const treePT treeP)
{
    return (tree_kids[(tree_trees[treeP].kidsKP) + 2]);
}

treePT tree_kid4TP (const treePT treeP)
{
    return (tree_kids[(tree_trees[treeP].kidsKP) + 3]);
}

treePT tree_kid5TP (const treePT treeP)
{
    return (tree_kids[(tree_trees[treeP].kidsKP) + 4]);
}

treePT tree_kid6TP (const treePT treeP)
{
    return (tree_kids[(tree_trees[treeP].kidsKP) + 5]);
}

treePT tree_kid7TP (const treePT treeP)
{
    return (tree_kids[(tree_trees[treeP].kidsKP) + 6]);
}

void tree_makeOneKid (treePT parentTP, const treePT babyTP)
{
    tree_trees[parentTP].kidsKP = tree_newKid ();
    tree_kids[tree_trees[parentTP].kidsKP] = babyTP;
    tree_trees[parentTP].count = 1;
}

void tree_makeTwoKids (treePT parentTP, const treePT buddyTP, const treePT sisTP)
{
    tree_trees[parentTP].kidsKP = tree_newKids (2);
    tree_trees[parentTP].count = 2;
    tree_kids[tree_trees[parentTP].kidsKP] = buddyTP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 1] = sisTP;
}

void tree_makeThreeKids (treePT parentTP, const treePT kid1TP, const treePT kid2TP, const treePT kid3TP)
{
    tree_trees[parentTP].kidsKP = tree_newKids (3);
    tree_trees[parentTP].count = 3;
    tree_kids[tree_trees[parentTP].kidsKP] = kid1TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 1] = kid2TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 2] = kid3TP;
}

void tree_makeFourKids (treePT parentTP, const treePT kid1TP, const treePT kid2TP, const treePT kid3TP, const treePT kid4TP)
{
    tree_trees[parentTP].kidsKP = tree_newKids (4);
    tree_trees[parentTP].count = 4;
    tree_kids[tree_trees[parentTP].kidsKP] = kid1TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 1] = kid2TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 2] = kid3TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 3] = kid4TP;
}

void tree_makeFiveKids (treePT parentTP, const treePT kid1TP, const treePT kid2TP, const treePT kid3TP, const treePT kid4TP, const treePT kid5TP)
{
    tree_trees[parentTP].kidsKP = tree_newKids (5);
    tree_trees[parentTP].count = 5;
    tree_kids[tree_trees[parentTP].kidsKP] = kid1TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 1] = kid2TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 2] = kid3TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 3] = kid4TP;
    tree_kids[(tree_trees[parentTP].kidsKP) + 4] = kid5TP;
}

bool tree_plural_emptyP (const treePT pluralTP)
{
    return (tree_trees[tree_kids[tree_trees[pluralTP].kidsKP]].kind == treeKind_empty);
}

treePT tree_plural_firstTP (const treePT pluralTP)
{
    return (tree_kids[tree_trees[tree_kids[tree_trees[pluralTP].kidsKP]].kidsKP]);
}

treePT tree_plural_restTP (const treePT pluralTP)
{
    return (tree_kids[(tree_trees[tree_kids[tree_trees[pluralTP].kidsKP]].kidsKP) + 1]);
}

// Extract a subtree

static tokenT tree_extract_XT;
static tokenT tree_extract_repeatXT;

static void tree_real_extract (const treePT scopeTP, const bool mustCopy, const bool recursive, treePT *resultRepeatTP)
{
    // Stack use limitation - to avoid crashes
    checkstack ();

    // extract all the occurences of things of type [X]
    // from the scope and append them to a result [repeat X]
    treePT nextResultRepeatTP = *resultRepeatTP;
    bool mustCopyKids = mustCopy;

    if (((tree_trees[scopeTP].name == tree_extract_XT) 
                && (tree_trees[scopeTP].kind < firstLeafKind))            // don't mistake token for type
            || (kindType[tree_trees[scopeTP].kind] == tree_extract_XT)) { // unless that's what we're looking for

        // append onto the end of the result so far - re-use empty kids
        treePT repeatTP = tree_newTreeInit (treeKind_repeat, tree_extract_repeatXT, tree_extract_repeatXT, 
            2, tree_trees[*resultRepeatTP].kidsKP);

        // we must copy the extracted tree so as not to create any DAGs
        // unless we are explicitly told it is ok
        treePT scopeCopyTP = scopeTP;
        if (mustCopy) {
            tree_copyTree (scopeTP, &(scopeCopyTP));
        } else {
            mustCopyKids = true;
        }

        tree_makeTwoKids (*resultRepeatTP, scopeCopyTP, repeatTP);
        nextResultRepeatTP = repeatTP;

        // if it's a shallow extract, don't look inside
        if (! recursive) {
            return;
        }
    }

    if (tree_trees[scopeTP].kind == treeKind_choose) {
        tree_real_extract (tree_kids[tree_trees[scopeTP].kidsKP], mustCopyKids, recursive, &(nextResultRepeatTP));

    } else if ((tree_trees[scopeTP].kind == treeKind_order) 
            || (tree_trees[scopeTP].kind == treeKind_repeat) 
            || (tree_trees[scopeTP].kind == treeKind_list)) {

        kidPT scopeKidsKP = tree_trees[scopeTP].kidsKP;

        for (int k = 1; k <= tree_trees[scopeTP].count; k++) {
            tree_real_extract (tree_kids[scopeKidsKP], mustCopyKids, recursive, &(nextResultRepeatTP));
            while (true) {
                if (tree_kids[tree_trees[nextResultRepeatTP].kidsKP] == emptyTP) break;
                nextResultRepeatTP = tree_kid2TP (nextResultRepeatTP);
            }
            scopeKidsKP++;
        }
    }
}

void tree_extract (const tokenT XT, const tokenT repeatXT, const treePT scopeTP, const bool mustCopy, const bool recursive, treePT *resultRepeatTP)
{
    // extract all the occurences of things of type [X]
    // from the scope and append them to a result [repeat X]

    // begin by setting the necessary type names
    tree_extract_XT = XT;
    tree_extract_repeatXT = repeatXT;

    // The following logic forces the extract to be done to a temporary, 
    // without destroying the original target tree until the extract is completely successfully done.
    // This makes extract an atomic operation, which is necessary for garbage collection.
    
    // create the default (empty) result
    treePT atomicResultRepeatTP = tree_newTreeInit (treeKind_repeat, tree_extract_repeatXT, tree_extract_repeatXT, 0, nilKid);
    tree_makeTwoKids (atomicResultRepeatTP, emptyTP, emptyTP);

    // now do the actual extraction
    tree_real_extract (scopeTP, mustCopy, recursive, &(atomicResultRepeatTP));
    *resultRepeatTP = atomicResultRepeatTP;
}

void tree_substitute (const treePT oldTP, const treePT newTP, treePT *scopeTP)
{
    checkstack ();
 
    // substitute all occurrences of old by new
    if (tree_sameTrees (*scopeTP, oldTP)) {
        // we must copy the new tree so as not to create any DAGs
        tree_copyTree (newTP, scopeTP);
        // don't do it inside the subsituted one!

    } else if (tree_trees[*scopeTP].kind == treeKind_choose) {
        tree_substitute (oldTP, newTP, &(tree_kids[tree_trees[*scopeTP].kidsKP]));

    } else if (tree_trees[*scopeTP].kind == treeKind_order) {
        kidPT scopeKidsKP = tree_trees[*scopeTP].kidsKP;
        for (countT k = 1; k <= tree_trees[*scopeTP].count; k++) {
            tree_substitute (oldTP, newTP, &(tree_kids[scopeKidsKP]));
            scopeKidsKP++;
        }

    } else if ((tree_trees[*scopeTP].kind == treeKind_repeat) || (tree_trees[*scopeTP].kind == treeKind_list)) {
        kidPT scopeKidsKP = tree_trees[*scopeTP].kidsKP;
        if (tree_trees[oldTP].name == tree_trees[*scopeTP].name) {
            tree_substitute (oldTP, newTP, &(tree_kids[scopeKidsKP]));
            tree_substitute (oldTP, newTP, &(tree_kids[scopeKidsKP + 1]));
        } else {
            while (true) {
                tree_substitute (oldTP, newTP, &(tree_kids[scopeKidsKP]));
                if (tree_trees[tree_kids[scopeKidsKP + 1]].kind == treeKind_empty) break;
                scopeKidsKP = tree_trees[tree_kids[scopeKidsKP + 1]].kidsKP;
            }
        }
    }
}

void tree_substituteLiteral (const treePT oldTP, const treePT newTP, treePT *scopeTP)
{
    checkstack ();

    if (tree_trees[*scopeTP].kind == treeKind_choose) {
        int skipTP = *scopeTP;
        while (true) {
            if (tree_trees[tree_kids[tree_trees[skipTP].kidsKP]].kind != treeKind_choose) break;
            skipTP = tree_kids[tree_trees[skipTP].kidsKP];
        }
        tree_substituteLiteral (oldTP, newTP, &(tree_kids[tree_trees[skipTP].kidsKP]));

    } else if (tree_trees[*scopeTP].kind == treeKind_order) {
        int scopeKidsKP = tree_trees[*scopeTP].kidsKP;
        for (countT k = 1; k <= tree_trees[*scopeTP].count; k++) {
            tree_substituteLiteral (oldTP, newTP, &(tree_kids[scopeKidsKP]));
            scopeKidsKP++;
        }

    } else if ((tree_trees[*scopeTP].kind == treeKind_repeat) || (tree_trees[*scopeTP].kind == treeKind_list)) {
        kidPT scopeKidsKP = tree_trees[*scopeTP].kidsKP;
        assert (scopeKidsKP != nilKid);
        while (true) {
            tree_substituteLiteral (oldTP, newTP, &(tree_kids[scopeKidsKP]));
            if (tree_trees[tree_kids[scopeKidsKP + 1]].kind == treeKind_empty) break;
            scopeKidsKP = tree_trees[tree_kids[scopeKidsKP + 1]].kidsKP;
        }

    } else if ((tree_trees[*scopeTP].kind == tree_trees[oldTP].kind) 
            && (tree_trees[*scopeTP].name == tree_trees[oldTP].name)) {
        *scopeTP = newTP;
    }
}

bool tree_isListOrRepeat (const treePT listOrRepeatTP)
{
    // repeat_0_X, repeat_1_X, list_0_X, list_1_X ?
    longstring *name = ident_idents[tree_trees[listOrRepeatTP].name];

    if (lstringchar (*name, 1) == 'r') {
        return (stringncmp (name, "repeat_", 7) == 0);
    } else if (lstringchar (*name, 1) == 'l') {
        return (stringncmp (name, "list_", 5) == 0);
    } else {
        return (false);
    }
}

int tree_lengthListOrRepeat (const treePT listOrRepeatTP)
{
    // return the number of elements in a [list X] or [repeat X]
    assert (tree_isListOrRepeat (listOrRepeatTP));

    // repeat_0_X, repeat_1_X, list_0_X, list_1_X
    longstring *name = ident_idents[tree_trees[listOrRepeatTP].name];

    if (tree_trees[tree_kids[tree_trees[listOrRepeatTP].kidsKP]].kind == treeKind_empty) {
        return (0);
    } else {
        int repeatCount = 1;
        treePT  runTP;

        if (lstringchar (*name, 8) == '1') {
            runTP = tree_kid2TP (listOrRepeatTP);
        } else {
            runTP = tree_kid2TP (tree_kids[tree_trees[listOrRepeatTP].kidsKP]);
        }

        while (true) {
            if (tree_plural_emptyP (runTP)) break;
            repeatCount++;
            runTP = tree_plural_restTP (runTP);
        }
        return (repeatCount);
    }
}

bool tree_isEmptyListOrRepeat (const treePT listOrRepeatTP)
{
    assert (tree_isListOrRepeat (listOrRepeatTP));
    return (tree_trees[tree_kids[tree_trees[listOrRepeatTP].kidsKP]].kind == treeKind_empty);
}

treePT tree_listOrRepeatFirstTP (const treePT listOrRepeatTP)
{
    assert (tree_isListOrRepeat (listOrRepeatTP));
    return (tree_kid1TP (listOrRepeatTP));
}

treePT tree_listOrRepeatRestTP (const treePT listOrRepeatTP)
{
    assert (tree_isListOrRepeat (listOrRepeatTP));
    return (tree_kid2TP (listOrRepeatTP));
}

bool tree_isListOrRepeatType (const tokenT listOrRepeatType)
{
    // repeat_0_X, repeat_1_X, list_0_X, list_1_X ?
    longstring *name = ident_idents[listOrRepeatType];
    if (lstringchar (*name, 1) == 'r') {
        return (stringncmp (name, "repeat_", 7) == 0);
    } else if (lstringchar (*name, 1) == 'l') {
        return (stringncmp (name, "list_", 5) == 0);
    } else {
        return (false);
    }
}

tokenT tree_listOrRepeatBaseType (const tokenT listOrRepeatType)
{
    assert (tree_isListOrRepeatType (listOrRepeatType));

    // repeat_0_X, repeat_1_X, list_0_X, list_1_X 
    string typeName, baseTypeName;
    stringcpy (typeName, *ident_idents[listOrRepeatType]);

    if (lstringchar (typeName, 1) == 'r') {
        // repeat_?_X
        stringcpy (baseTypeName, &(lstringchar (typeName, 10)));
        stringcpy (typeName, baseTypeName);
    } else {
        // list_?_X
        stringcpy (baseTypeName, &(lstringchar (typeName, 8)));
        stringcpy (typeName, baseTypeName);
    }

    const int identIndex = ident_install (typeName, treeKind_id);

    return (identIndex);
}

// Tree type matchers - used in compiler, transformer and predefineds

bool tree_treeIsTypeP (const treePT treeP, const tokenT typeT)
{
    // used only in matching variables (typeT) to patterns (treeP) when parsing patterns
    if ((tree_trees[treeP].kind != treeKind_literal) && 
            ((((tree_trees[treeP].name) == typeT) || (typeT == any_T)) || ((kindType[(tree_trees[treeP].kind)]) == typeT))) {
        return (true);

    } else if ((tree_trees[treeP].kind == treeKind_repeat) || (tree_trees[treeP].kind == treeKind_generaterepeat)) {
        // repeat_?_X
        return ((stringncmp (ident_idents[typeT], "repeat_", 7) == 0) 
            // type cheat to compare base type X of repeat_0_X
            && (stringcmp (&(lstringchar (*ident_idents[tree_trees[treeP].name], 10)), &(lstringchar (*ident_idents[typeT], 10))) == 0)
            // matches [repeat X+] only if non-empty
            && ((lstringchar (*ident_idents[typeT], 8) != '1') || (tree_trees[tree_kid1TP (treeP)].kind != treeKind_empty)));

    } else if (((tree_trees[treeP].kind) == treeKind_list) || ((tree_trees[treeP].kind) == treeKind_generatelist)) {
        // list_?_X
        return ((stringncmp (ident_idents[typeT], "list_", 5) == 0) 
            // type cheat to compare base type X of list_0_X
            && (stringcmp (&(lstringchar (*ident_idents[tree_trees[treeP].name], 8)), &(lstringchar (*ident_idents[typeT], 8))) == 0)
            // matches [list X+] only if non-empty
            && ((lstringchar (*ident_idents[typeT], 6) != '1') || (tree_trees[tree_kid1TP (treeP)].kind != treeKind_empty)));
    }

    return (false);
}

tokenT tree_literalTypeName (const enum treeKindT kind)
{
    // used in compiling rules and external function [parse]
    return (kindType[kind]);
}

// Initialization
void tree (void) {
    assert ((AVAILABLE > maxTrees) && (AVAILABLE > maxKids));

    stringprintf (outOfTreesMessage, "Out of tree space - %d trees have been allocated.", maxTrees);
    stringprintf (outOfKidsMessage, "Out of kid space - %d kids have been allocated.", maxKids);

    // 1-origin [1 .. maxKids]
    arrayalloc (maxKids + 1, treePT, tree_kids);
    tree_kidCount = 0;
    tree_kids[0] = UNUSED;

    // 1-origin [1 .. maxTrees]
    arrayalloc (maxTrees + 1, struct parseTreeT, tree_trees);
    tree_treeCount = 0;
    tree_maxTreeCount = tree_treeCount;
    tree_trees[0].name = UNUSED;

    tree_allocationStrategy = simple;

    tree_lookTree = 0;
    tree_lookKid = 0;

    tree_firstUserTree = 0;
    tree_firstUserKid = 0;
}
